package com.demo.sort;

import com.demo.sort.base.SortBase;
import org.junit.jupiter.api.Test;

/**
 * 希尔排序 (递减增量排序算法)
 * 是【插入排序】的一种更高效的改进版本。但希尔排序是非稳定排序算法。
 * 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
 * 待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
 *
 * 思路:  多次分组进行插入排序
 * 1. 首先确定步长（当前数组长度的一半）
 * 2. 通过步长来确定分组
 * 3. 在分组内进行插入排序 (达到宏观有序)
 * 4. 当只有一个分组时(步长为1时，此时已基本有序了)，再一次插入排序完成
 *
 * 分析:
 * 时间复杂度    O(n log n)
 * 空间复杂度    O(1)
 *
 * @author huangChao
 **/
public class ShellSort extends SortBase {

    @Test
    public void app() throws Exception {
        handler(this::sort);
        handler(this::swapSort);
    }

    /**
     * 移动法
     */
    public int[] sort(int[] init) {
        for(int len = init.length, step = len / 2, temp; step > 0; step /= 2) {
            for(int i = step; i < len; i++) {
                // 中位数
                temp = init[i];
                // 移动下标
                int moveIndex = i;
                // 分组中下一个数下标
                int nextIndex = i - step;
                // 当左边值大于中位值则移动到右边
                while (nextIndex >= 0 && init[nextIndex] > temp) {
                    init[moveIndex] = init[nextIndex];
                    nextIndex -= step;
                    moveIndex -= step;
                }
                // 恢复值临时值
                if (i != moveIndex) {
                    init[moveIndex] = temp;
                }
            }
        }
        return init;
    }

    /**
     * 交换法
     */
    public int[] swapSort(int[] init) {
        for(int len = init.length, step = len / 2; step > 0; step /= 2) {
            for(int i = step, j, startIndex; i < len; i++) {
                j = i;
                while ((startIndex = (j - step)) >= 0 && init[j] < init[startIndex]) {
                    swap(init, j, startIndex);
                    j -= step;
                }
            }
        }
        return init;
    }
}
